Insufficient nodes in root to leaf paths [DFS]

Time: O(N); Space: O(H); medium

Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf. (A leaf is a node with no children.)

A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.

Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

Example 1:

Input: root = {TreeNode} [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1

Output: {TreeNode} [1,2,3,4,null,null,7,8,9,null,14]

Example 2:

Input: root = {TreeNode} [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22

Output: {TreeNode} [5,4,8,11,null,17,4,7,null,null,null,5]

Example 3:

Input: root = {TreeNode} [1,2,-3,-5,null,4,null], limit = -1

Output: {TreeNode} [1,null,-3,4]

Constraints:

• The given tree will have between 1 and 5000 nodes.

• -10^5 <= node.val <= 10^5

• -10^9 <= limit <= 10^9

Hints:

1. Consider a DFS traversal of the tree. You can keep track of the current path sum from root to this node, and you can also use DFS to return the minimum value of any path from this node to the leaf. This will tell you if this node is insufficient.

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Auxiliary Tools

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

1. Depth First Search

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def sufficientSubset(self, root, limit):
        """
        :type root: TreeNode
        :type limit: int
        :rtype: TreeNode
        """
        if not root:
            return None

        if not root.left and not root.right:
            return None if root.val < limit else root

        root.left = self.sufficientSubset(root.left, limit-root.val)
        root.right = self.sufficientSubset(root.right, limit-root.val)

        if not root.left and not root.right:
            return None
        return root

s = Solution1()

# [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14]
root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.left, root.left.right = TreeNode(4), TreeNode(-99)
root.right.left, root.right.right = TreeNode(-99), TreeNode(7)
root.left.left.left, root.left.left.right = TreeNode(8), TreeNode(9)
root.left.right.left, root.left.right.right = TreeNode(-99), TreeNode(-99)
root.right.left.left, root.right.left.right = TreeNode(12), TreeNode(13)
root.right.right.left, root.right.right.right = TreeNode(-99), TreeNode(14)
limit = 1
t = TreeTasks()
dot = t.visualize_tree(root)   # check the input
tree = s.sufficientSubset(root, limit)
t = TreeTasks()
dot = t.visualize_tree(tree)

# [5,4,8,11,null,17,4,7,1,null,null,5,3]
root = TreeNode(5)
root.left, root.right = TreeNode(4), TreeNode(8)
root.left.left = TreeNode(11)
root.right.left, root.right.right = TreeNode(17), TreeNode(4)
root.left.left.left, root.left.left.right = TreeNode(7), TreeNode(1)
root.right.right.left, root.right.right.right = TreeNode(5), TreeNode(3)
limit = 22
t = TreeTasks()
dot = t.visualize_tree(root)   # check the input
tree = s.sufficientSubset(root, limit)
t = TreeTasks()
dot = t.visualize_tree(tree)

# [1,2,-3,-5,null,4,null]
root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(-3)
root.left.left = TreeNode(-5)
root.right.left = TreeNode(4)
limit = -1
t = TreeTasks()
dot = t.visualize_tree(root)   # check the input
tree = s.sufficientSubset(root, limit)
t = TreeTasks()
dot = t.visualize_tree(tree)

See also:

https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths